The present invention generally relates to modeling processes, in such fields as those derived from physical, chemical, biological, financial and sundry conceptual mathematical systems. More particularly, the present invention relates to a method and apparatus for modeling processes using a multi-state dynamical system, such as cellular automata.
Differential and integral equations result from the mathematical modeling of processes. For most complex phenomena, the number of independent variables (e.g., spatial coordinates and time) is more than one, and the full description of the process will require more than one dependent variable (e.g., velocity, temperature, displacement, stress). The governing equations for such processes are expressible in the form of partial differential equations (PDEs). These equations indicate the dependence of the characteristics of the process on the plethora of independent variables. For many physical phenomena, PDEs emerge from a continuum viewpoint. The continuum equations derive from statistical averaging of microscopic phenomena. For example, consider a physical process such as the movement of fluid in a container. We can look at the forces acting on small element of this fluid. This representative elementary volume, REV, should be small enough to allow us to say we are observing the flow at a point; but large enough to make a statistical averaging of the microscopic events meaningful. When statements pertaining to the conservation of mass, momentum and energy for this element are written, the result will be partial differential equations. Examples include the Navier-Stokes equations, Laplace""s equation, Poisson equation, etc.
The common approach to solving these PDEs is the use of numerical techniques (e.g., finite difference, finite element, finite volume, method of characteristics, etc.) to integrate the pertinent continuum partial differential equations. Tremendous human and financial resources have been expended in the development of these computational methods.
Prior art involved a traditional approach to Cellular Automata (CA) Modeling. CA modeling, thc basis of the legendary lattice-gas methods, involves the application of the evolving fields of cellular automata to represent the process being studicd. The traditional CA modeling approach stands somewhere between the microscopic viewpoint and the continuum approach. In applying CA to a physical problem, an association must be established between known physical quantities of the problem and those calculated as a result of repeated iteration (using the CA rule) from a set of initial conditions. The process of relating particular CA rules to specific problems is not trivial. However, the association has already been made for a variety of complex nonlinear problems including hydrodynamics, flows in porous media, chemical turbulence, percolation and nucleation, diffusion-controlled reactions, and dynamical systems. Cellular Automata represent a serious and highly effective tool for studying the microscopic character of transport processes, and for solving the associated macroscopic (continuum) equations.
CA-based modeling offers advantages both in the representation of the underlying (physical, chemical, biological, etc.) process, and in the numerical solution of the problem. For example, the 1986 work of Frisch, Hasslacher, Pomeau (FHP) provided perhaps the first serious effort at using a CA-based method to solve the full Navier-Stokes equations. The fluid is represented by particles of unit mass and momentum moving in a triangular lattice. On reaching a node in the lattice, the particles go through a collision process in which there is redistribution along the available directions. The total mass and momentum is preserved at each node. Large-scale averages taken from the lattices are solutions to the full Navier-Stokes equations in an asymptotic limit.
The FHP work has had a significant impact on other CA-based modeling. For example, others have examined the potential applications of CA methods to the fluid flow in complex porous media, and have investigated CA models for simulating coupled solute transport and chemical reactions at mineral surfaces and in pore networks.
Amongst prior inventions that utilize variants of the lattice-gas approach in CA modeling include those taught by Wolfram (U.S. Pat. No. 4,809,202), Chen et al (U.S. Pat. No. 5,594,671), Traub et al (U.S. Pat. No. 5,606,517), Chen et al (U.S. Pat. No. 5,848,260), and Teixeira et al (U.S. Pat. No. 5,953,239).